package unionFind

/*
时间复杂度：O(n)
空间复杂度:O(n)
*/

func longestConsecutive(nums []int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	m := make(map[int]int, 0)
	for _, v := range nums {
		m[v] = v + 1
	}
	res := 1
	for _, v := range nums {
		if _, ok := m[v-1]; ok {
			continue
		}
		l := findRoot(m, m[v]) - v
		if res < l {
			res = l
		}
	}
	return res
}

// 找到连续数字中最大的一个
func findRoot(m map[int]int, v int) int {
	if _, ok := m[v]; !ok {
		return v
	}
	return findRoot(m, m[v])
}

// 先找到连续序列中最小的一个数据，然后根据map每次判断连续序列中的下一个数字是否存在，最后找到连续序列中最大的数字
// 再从最小找最大的过程中，累加连续序列的长度
func longestConsecutive1(nums []int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	m := make(map[int]bool)
	for _, v := range nums {
		m[v] = true
	}
	maxLen := 1
	for v := range m {
		// 如果存在比v要小的连续数字，则返回
		// 这一步是为了找到连续数字中最小的一个，因为如果存在连续数字，且x不为最小的一个，则一定存在x-1
		if m[v-1] {
			continue
		}
		curNum := v
		curLen := 1
		for m[curNum+1] {
			curNum++
			curLen++
		}
		if maxLen < curLen {
			maxLen = curLen
		}
	}
	return maxLen
}

// 并查集
func longestConsecutive2(nums []int) int {
	if nums == nil || len(nums) == 0 {
		return 0
	}
	uf := &UnionFind4{}
	uf.init(nums)
	maxLen := 1

	for _, v := range nums {
		curLen := uf.Find(v) - v
		if maxLen < curLen {
			maxLen = curLen
		}
	}
	return maxLen
}

// 并查集
type UnionFind4 struct {
	Parent map[int]int
}

// 初始化时将节点x的父节点设置为x+1，然后可以根据Find方法找到连续序列中的最大值
func (u *UnionFind4) init(nums []int) {
	u.Parent = make(map[int]int)
	for _, v := range nums {
		u.Parent[v] = v + 1
	}
}

// 路径压缩-将x的父节点设置为x所在集合的根节点
func (u *UnionFind4) Find(x int) int {
	if _, ok := u.Parent[x]; !ok {
		return x
	}
	u.Parent[x] = u.Find(u.Parent[x])
	return u.Parent[x]
}
